package cn.fansunion.leecode.number;

/**
 * 1539. 第 k 个缺失的正整数 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
 * 
 * 请你找到这个数组里第 k 个缺失的正整数。 https://leetcode-cn.com/problems/kth-missing-positive-number/
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-19
 */
public class KthMissingPositiveNumber {
    /* 示例 1：
    
    输入：arr = [2,3,4,7,11], k = 5
    输出：9
    解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。
    示例 2：
    
    输入：arr = [1,2,3,4], k = 2
    输出：6
    解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。
     
    
    提示：
    
    1 <= arr.length <= 1000
    1 <= arr[i] <= 1000
    1 <= k <= 1000
    对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 
    */
    /**
     * 思路：从1到x遍历数组，数组中找到当前n值，就下一个；找不到，漏掉+1；<br/>就网上的很多代码，可读性差的要死
     * @param arr
     * @param k
     * @return
     */
    public int findKthPositive(int[] arr, int k) {
        //漏掉的数目
        int skip = 0;
        //数组中的元素，匹配到的个数（下标，逐步向后，但不一定每一次都命中-向后移）
        int arrMatchIndex = 0;
        //n<=1000不对，改成了“arr.length+k”，不一定非常精确
        for (int n = 1; n <= arr.length+k; n++) {
            //arr越界了，漏掉的数字+1
            if (arrMatchIndex >= arr.length) {
                skip++;
            } else {
                //arr没越界，数字不相等，漏掉的数字+1
                if (n == arr[arrMatchIndex]) {
                    arrMatchIndex++;
                } else {
                    skip++;
                }
            }
            //漏掉第k次，n就是那个数字
            if (skip == k) {
                return n;
            }
        }
        return -1;

    }
}
